#include <queue>
#include <stack>

using namespace std;

// 用栈实现队列
// 测试链接 : https://leetcode.cn/problems/implement-queue-using-stacks/
class MyQueue 
{
private:
    stack<int> in;
    stack<int> out;

public:
    MyQueue() 
    {}
    
    // 倒数据
    // 从 in 栈，把数据倒入 out 栈
    // 1) out 空了，才能倒数据
    // 2) 如果倒数据，in 必须倒完
    void inToOut()
    {
        if(out.empty())
        {
            while(!in.empty())
            {
                out.push(in.top());
                in.pop();
            }
        }
    }

    void push(int x) 
    {
        in.push(x);
        inToOut();
    }

    int pop() 
    {
        inToOut();
        int ans = out.top();
        out.pop();
        return ans;
    }
    
    int peek() 
    {
        inToOut();
        return out.top();
    }
    
    bool empty() 
    {
        return in.empty() && out.empty();
    }
};


// 用队列实现栈（一个队列）
// 测试链接 : https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack 
{
private:
    queue<int> q;

public:
    MyStack() 
    {}
    
    // O(n)
    void push(int x) 
    {
        int n = q.size();
        q.push(x);
        for(int i = 0; i < n; ++i)
        {
            q.push(q.front());
            q.pop();
        }
    }
    
    int pop() 
    {
        int ans = q.front();
        q.pop();
        return ans;
    }
    
    int top() 
    {
        return q.front();
    }
    
    bool empty() 
    {
        return q.empty();
    }
};

// 用队列实现栈（两个队列）
// 两个队列实现栈的核心就是始终至少维持一个队列为空
// 测试链接 : https://leetcode.cn/problems/implement-stack-using-queues/
class MyStack 
{
private:
    queue<int> q1;
    queue<int> q2;

public:
    MyStack() 
    {}
    
    void push(int x) 
    {
        // 往不为空的队列中入数据
        if(!q1.empty()) 
        {
            q1.push(x);
        }
        else 
        {
            q2.push(x);
        }
    }
    
    int pop() 
    {
        // 找出谁是空队列，默认 q1 为空队列
        if(!q1.empty()) q1.swap(q2);

        while(q2.size() > 1)
        {
            q1.push(q2.front());
            q2.pop();
        }

        int ans = q2.front();
        q2.pop();
        return ans;
    }
    
    int top() 
    {
        if(!q1.empty())
        {
            return q1.back();
        }
        else
        {
            return q2.back();
        }
    }
    
    bool empty() 
    {
        return q1.empty() && q2.empty();
    }
};